package br.ufrn.ciencomp.grafos;

import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;

import br.ufrn.ciencomp.conjuntos.Conjunto;
import br.ufrn.ciencomp.grafos.Grafo.Tipo;

public class AGM {
	
	private static LinkedList<Aresta> quickSort(LinkedList<Aresta> arestas) {
		if(arestas.size() < 1)
			return arestas;
		
		Aresta pivo = arestas.get(0);
		LinkedList<Aresta> menor = new LinkedList<Aresta>();
		LinkedList<Aresta> pivos = new LinkedList<Aresta>();
		LinkedList<Aresta> maior = new LinkedList<Aresta>();
		
		for(Aresta a : arestas) {
			if(a.getPeso() < pivo.getPeso()) {
				menor.add(a);
			} else if(a.getPeso() > pivo.getPeso()){
				maior.add(a);
			} else {
				pivos.add(a);
			}
		}
		
		menor = quickSort(menor);
		maior = quickSort(maior);
		
		menor.addAll(pivos);
		menor.addAll(maior);
		return menor;
		
	}
	
	public static LinkedList<Aresta> kruskal(Grafo g) {
		LinkedList<Aresta> arestasOrdenadas = quickSort(g.getArestas());
		LinkedList<Aresta> agm = new LinkedList<Aresta>();
		Conjunto c = new Conjunto(g.getN());
		
		for(Aresta a : arestasOrdenadas) {
			if(c.findSet(a.getOrigem()) !=
				c.findSet(a.getDestino())) {
				agm.add(a);
				c.union(a.getOrigem(), a.getDestino());
			}
		}
		
		return agm;
	}
	
	/*
	public static LinkedList<Aresta> prim(Grafo g) {
		//Fazer fila de prioridade antes!
		/*
			Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
			Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
			Repeat until Vnew = V:
			Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)
			Add v to Vnew, and {u, v} to Enew
			Output: Vnew and Enew describe a minimal spanning tree
	}
	*/
	
	public static void main(String args[]) {
		try {
			Scanner scanner = new Scanner(new File("streams/agm3.in"));
			
			Grafo g = new Grafo(scanner.nextInt(), Tipo.LISTA);
			
			while(scanner.hasNext()) {
				String instrucao = scanner.next();
				if(instrucao.startsWith("edge")) {
					g.addAresta(
							scanner.nextInt(), 
							scanner.nextInt(), 
							scanner.nextInt());
				} else if(instrucao.equals("kruskal")) {
					LinkedList<Aresta> agm = kruskal(g);
					int pesoTotal = 0;
					for(Aresta a : agm) {
						System.out.println(a.getOrigem() + " " + a.getDestino());
						pesoTotal += a.getPeso();
					}
					System.out.println(pesoTotal);
				} else if(instrucao.equals("prim")) {
					/*
					LinkedList<Aresta> agm = prim(g);
					int pesoTotal = 0;
					for(Aresta a : agm) {
						System.out.println(a.getOrigem() + " " + a.getDestino());
						pesoTotal += a.getPeso();
					}
					System.out.println(pesoTotal);
					*/
				}
			}
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
}
